#include <algorithm>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/*
 * @lc app=leetcode.cn id=86 lang=cpp
 *
 * [86] 分隔链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // 使用快排的思想
    // ListNode* partition(ListNode* head, int x) {
    //     ListNode node; node.next = head;
    //     ListNode *last_least = head, *cur = head;
    //     while (cur) {
    //         if (cur->val < x) {
    //             swap(cur->val, last_least->val);
    //             last_least = last_least->next;
    //         }
    //         cur = cur->next;
    //     }
    //     return head;
    // }

    ListNode* partition(ListNode* head, int x) {
        ListNode small, large;
        ListNode *s = &small, *l = &large, *cur = head;
        while (cur) {
            if (cur->val < x) {
                s->next = cur; s = s->next;
            }
            else {
                l->next = cur; l = l->next;
            }
            cur = cur->next;
        }
        s->next = large.next; l->next = nullptr;
        return small.next;
    }

};
// @lc code=end

